package main.Q401_500;

import java.util.HashMap;
import java.util.Map;

public class Q461_470 {
    public static void main(String[] args) {
        System.out.println("Question461：汉明距离");
        System.out.println("Question462：");
        System.out.println("Question463：岛屿的周长");
        System.out.println("Question464：我能赢吗");
        System.out.println("Question465：");
        System.out.println("Question466：统计重复个数");
        System.out.println("Question467：");
        System.out.println("Question468：");
        System.out.println("Question469：");
        System.out.println("Question470：用Rand7()实现Rand10()");
    }
}

class Question461 {
    public static int hammingDistance(int x, int y) {
        return Integer.bitCount(x ^ y);
    }
}

class Question463 {
    public static int islandPerimeter(int[][] grid) {//未解决
        int lengthOfLand = 0;
        for (int i = 0; i < grid.length; i++) {
            for (int j = 0; j < grid.length; j++) {
                if (grid[i][j] == 1) {//为陆地时
                    int count = 0;//计算四周水域数
                    if ((i - 1 >= 0 && grid[i - 1][j] == 0) || i - 1 < 0) count++;//判断上方是否为水域
                    if ((j + 1 < grid.length && grid[i][j + 1] == 0) || j + 1 >= grid.length) count++;//判断右方是否为水域
                    if ((i + 1 < grid.length && grid[i + 1][j] == 0) || i + 1 >= grid.length) count++;//判断下方是否为水域
                    if ((j - 1 >= 0 && grid[i][j - 1] == 0) || j - 1 < 0) count++;//判断左方是否为水域
                    lengthOfLand += count;
                }
            }
        }
        return lengthOfLand;
    }
}

class Question464 {
    public boolean first(int maxChoosableInteger, int desiredTotal) {
        if (maxChoosableInteger >= desiredTotal) return true;
        desiredTotal -= maxChoosableInteger;
        maxChoosableInteger--;
        if (second(maxChoosableInteger, desiredTotal)) return false;
        else return true;
    }

    public boolean second(int maxChoosableInteger, int desiredTotal) {
        if (maxChoosableInteger >= desiredTotal) return true;
        desiredTotal -= maxChoosableInteger;
        maxChoosableInteger--;
        if (first(maxChoosableInteger, desiredTotal)) return false;
        else return true;
    }

    public boolean canIWin(int maxChoosableInteger, int desiredTotal) {
        return first(maxChoosableInteger, desiredTotal);
    }
}

class Question466 {
    public int getMaxRepetitions(String s1, int n1, String s2, int n2) {
//        String str1 = "", str2 = "";//暴力求解
//        for (int i = 0; i < n1; i++) {
//            str1 = str1 + s1;
//        }
//        for (int i = 0; i < n2; i++) {
//            str2 = str2 + s2;
//        }
//        int result = 0, str2Index = 0;
//        for (int i = 0; i < str1.length(); i++) {
//            if (str1.charAt(i) == str2.charAt(str2Index)) {
//                str2Index++;
//            }
//            if (str2Index == str2.length()) {
//                result++;
//                str2Index = 0;
//            }
//        }
//        return result;
        if (n1 == 0) {
            return 0;
        }
        int s1cnt = 0, index = 0, s2cnt = 0;
        Map<Integer, int[]> recall = new HashMap<Integer, int[]>();
        int[] preLoop = new int[2];
        int[] inLoop = new int[2];
        while (true) {
            ++s1cnt;
            for (int i = 0; i < s1.length(); ++i) {
                char ch = s1.charAt(i);
                if (ch == s2.charAt(index)) {
                    index += 1;
                    if (index == s2.length()) {
                        ++s2cnt;
                        index = 0;
                    }
                }
            }
            if (s1cnt == n1) {
                return s2cnt / n2;
            }
            if (recall.containsKey(index)) {
                int[] value = recall.get(index);
                int s1cntPrime = value[0];
                int s2cntPrime = value[1];
                preLoop = new int[]{s1cntPrime, s2cntPrime};
                inLoop = new int[]{s1cnt - s1cntPrime, s2cnt - s2cntPrime};
                break;
            } else {
                recall.put(index, new int[]{s1cnt, s2cnt});
            }
        }
        int result = preLoop[1] + (n1 - preLoop[0]) / inLoop[0] * inLoop[1];
        int rest = (n1 - preLoop[0]) % inLoop[0];
        for (int i = 0; i < rest; ++i) {
            for (int j = 0; j < s1.length(); ++j) {
                char ch = s1.charAt(j);
                if (ch == s2.charAt(index)) {
                    ++index;
                    if (index == s2.length()) {
                        ++result;
                        index = 0;
                    }
                }
            }
        }
        return result / n2;
    }
}

class Question470 {
//    public int rand10() {
//        int base=rand7(),add=0,temp=0;
//        do {
//            temp=rand7();
//            if (temp==1) add=0;
//            else if (temp==2) add=1;
//            else if (temp==3) add=2;
//            else if (temp==4) add=4;
//        }while(temp==7||temp==6||temp==5);
//        return base+add;
//    }
}